Branch and price algorithms for the dual bin packing problem and the maximum cardinality bin packing problem

摘要

We present two efficient branch and price algorithms to solve the maximum cardinality and the dual bin packing problem. The general structure of the algorithms is similar and can be used for other one dimensional packing or cutting problems as well. We compare the performance of our algorithm with enumerative procedures for both problems. Branch and price outperforms the enumerative procedures.